class Solution {
public:
    bool isValid(string s) 
    {
        char c[10000];
        int tail=0;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='(' || s[i]=='{' || s[i]=='[')
            {
                c[tail++]=s[i];
            }
            else
            {
                if(tail==0)
                {
                    return false;
                }
                if(s[i]==')' && c[tail-1]!='(') return false;
                if(s[i]==']' && c[tail-1]!='[') return false;
                if(s[i]=='}' && c[tail-1]!='{') return false;
                tail--;
            }
        }
        if(tail!=0)
        {
            return false;
        }
        return true;
    }
};
